package com.xiaoyu.binaryTree;

/**
 * @program: DS_and_A
 * @description: 最长同值路径
 * 给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
 *
 * 注意：两个节点之间的路径长度由它们之间的边数表示。
 *
 * 示例 1:
 *
 * 输入:
 *
 *               5
 *              / \
 *             4   5
 *            / \   \
 *           1   1   5
 * 输出:
 *
 * 2
 *
 * @author: YuWenYi
 * @create: 2021-06-07 10:29
 **/
public class LongestUnivaluePath_687 {

    private int pathLen;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return pathLen;
    }

    public int dfs(TreeNode root){
        if (root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);

        int leftUniPath = 0,rightUniPath = 0;
        if (root.left != null && root.left.val == root.val){
            leftUniPath = left + 1;  //只有值相同才有资格去+1
        }
        if (root.right != null && root.right.val == root.val){
            rightUniPath = right + 1;
        }

        //比较双侧路径最大长度,为什么有相加? --> 因为路径就是左子树路径+右子树路径啊!
        pathLen = Math.max(leftUniPath + rightUniPath, pathLen);

        return Math.max(leftUniPath, rightUniPath);  //返回单侧路径最大长度
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(4,new TreeNode(5),new TreeNode(6));
        TreeNode right = new TreeNode(2);
        TreeNode left = new TreeNode(2,null,null);
        TreeNode root = new TreeNode(2,left,right);
        LongestUnivaluePath_687 longestUnivaluePath_687 = new LongestUnivaluePath_687();
        System.out.println(longestUnivaluePath_687.longestUnivaluePath(root));

    }
}
